翻訳と辞書
Words near each other
・ Closer to the Sun (Guy Sebastian album)
・ Closer to the Sun (Slightly Stoopid album)
・ Closer to the Truth
・ Closer to the Truth (Cher album)
・ Closer to the Truth (Tony Joe White album)
・ Closer to Truth
・ Closer to You
・ Closer to You (Carried Away album)
・ Closer to You (JJ Cale album)
・ Closer to You (The Coronas album)
・ Closer to Your Heart
・ Closer to Your Heart (Clannad song)
・ Closer to Your Heart (Natalie Grant song)
・ Closer/Sweet Dreams
・ Closers
Closest pair of points problem
・ Closest point method
・ Closest point problem
・ Closest string
・ Closest Thing to Heaven
・ Closest Thing to Heaven (album)
・ Closet
・ Closet (disambiguation)
・ Closet Cases of the Nerd Kind
・ Closet Children
・ Closet drama
・ Closet flange
・ Closet Land
・ Closet Monster
・ Closet Monster (film)


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Closest pair of points problem : ウィキペディア英語版
Closest pair of points problem

The closest pair of points problem or closest pair problem is a problem of computational geometry: given ''n'' points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane〔M. I. Shamos and D. Hoey. ("Closest-point problems." ) In ''Proc. 16th Annual IEEE Symposium on Foundations of Computer Science'' (FOCS), pp. 151—162, 1975 (DOI (10.1109/SFCS.1975.8 ))〕 was among the first geometric problems which were treated at the origins of the systematic study of the computational complexity of geometric algorithms.
A naive algorithm of finding distances between all pairs of points and selecting the minimum requires time. It turns out that the problem may be solved in time in a Euclidean space or Lp space of fixed dimension d. In the algebraic decision tree model of computation, the algorithm is optimal. The optimality follows from the observation that the element uniqueness problem (with the lower bound of for time complexity) is reducible to the closest pair problem: checking whether the minimal distance is 0 after the solving of the closest pair problem answers the question whether there are two coinciding points.
In the computational model which assumes that the floor function is computable in constant time the problem can be solved in time.〔S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979〕 If we allow randomization to be used together with the floor function, the problem can be solved in time.〔S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995〕〔(【引用サイトリンク】title=Rabin Flips a Coin )
==Brute-force algorithm==
The closest pair of points can be computed in O(''n''2) time by performing a brute-force search. To do that, one could compute the distances between all the pairs of points, then pick the pair with the smallest distance, as illustrated below.
''minDist'' = infinity
for ''i'' = 1 to length(''P'') - 1
for ''j'' = ''i'' + 1 to length(''P'')
let ''p'' = ''P''(), ''q'' = ''P''()
if ''dist''(''p'', ''q'') < ''minDist'':
''minDist'' = ''dist''(''p'', ''q'')
''closestPair'' = (''p'', ''q'')
return ''closestPair''

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Closest pair of points problem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.